Answering point-to-point distance queries in graphs is a fundamental building block for many applications in domains such as social networks, search, computational biology, computer networks, and road networks. Although distance queries can be answered by a well-known method attributed to Dijkstra in almost linear time, on large graphs this can take several seconds. This is too slow for most applications, which may need to run thousands or even millions of distance queries. For this reason, there has been steady progress in the design of more efficient techniques. The general approach is to build an index from the input graph to accelerate on-line queries. For complex networks, both exact and approximate algorithms have been developed.
As an example, on road networks, most recent algorithms are exact. Existing computer programs known as road-mapping programs provide digital maps, often complete with detailed road networks down to the city-street level. Typically, a user can input a location and the road-mapping program will display an on-screen map of the selected location. Several existing road-mapping products typically include the ability to calculate a best route between two locations. In other words, the user can input two locations, and the road-mapping program will compute the travel directions from the source location to the destination location. The directions are typically based on distance, travel time, and certain user preferences, such as a speed at which the user likes to drive, or the degree of scenery along the route. Computing the best route between locations may require significant computational time and resources.
Some programs compute shortest paths using variants of the Dijkstra method. Note that in this sense “shortest” means “least cost” because each segment (e.g., road segment) is assigned a cost or weight not necessarily directly related to the segment's length. By varying the way the cost is calculated for each segment, shortest paths can be generated for the quickest, shortest, or preferred routes. Dijkstra's original method, however, is not always efficient in practice, due to the large number of locations and possible paths that are scanned. Instead, many known programs use heuristic variations of Dijkstra's method.
More recent developments utilize a two-stage process comprising a preprocessing phase and a query phase. During the preprocessing phase, the graph or map is subject to an off-line processing such that later real-time queries between any two points (e.g., destinations) on the graph can be made more efficiently. Known examples of preprocessing algorithms use geometric information, hierarchical decomposition, and A* search.
Although there are many techniques that are specialized for some types of inputs, none of these techniques are robust to network structure, scale to large or massive networks, and are fast, straightforward, and efficient.